package de.hska.master.algo.mergeHull;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import de.hska.master.model.Model;
import de.hska.master.model.Point;
import de.hska.master.support.Geometry;

/**
 * Class which implements the merge hull algorithm.
 * 
 * @author julia
 * 
 */
public class MergeHullAlgorithm {

	private Model model = null;
	protected Geometry calculations = null;

	/**
	 * Constructor for the merge Hull Algorithm. Initializes the model the
	 * Geometry class.
	 * 
	 * @param model
	 */
	public MergeHullAlgorithm(Model model) {
		super();
		this.model = model;
		this.calculations = new Geometry();
	}

	public MergeHullAlgorithm() {
		super();
	}

	/**
	 * Runs the merge hull algorithm.
	 * 
	 * @return the points of the convex hull.
	 * @throws InterruptedException
	 */
	public List<Point> runAlgorithm() throws InterruptedException {
		List<Point> points = model.getPointsAsList();
		// sort with merge sort
		Collections.sort(points, new ComparableMergeHull());

		List<Point> mergedPoints = this.constructConvexHull(points);

		return mergedPoints;

	}

	/**
	 * Divide and conquer the points, construct the convex hull and merge the
	 * convex hulls.
	 * 
	 * @param points
	 *            all points
	 * @return the points of the convex hull.
	 */
	protected List<Point> constructConvexHull(List<Point> points) {

		if (points.size() <= 2) {
			return points;
		} else {
			DividedPoints dividedPoints = this.dividePoints(points);
			List<Point> left = constructConvexHull(dividedPoints.leftPoints);
			List<Point> right = constructConvexHull(dividedPoints.rightPoints);
			List<Point> mergedPoints = merge(left, right);
			return mergedPoints;
		}
	}

	protected List<Point> merge(List<Point> left, List<Point> right) {

		Boundary upperBoundary = getUpperBoundary(left, right);
		Boundary lowerBoundary = getLowerBoundary(left, right);

		List<Point> points = new ArrayList<Point>();

		for (int i = upperBoundary.indexRight; i != lowerBoundary.indexRight; i = getNextIndexClockwise(
				i, right.size())) {
			points.add(right.get(i));
		}
		points.add(right.get(lowerBoundary.indexRight));

		for (int i = lowerBoundary.indexLeft; i != upperBoundary.indexLeft; i = getNextIndexClockwise(
				i, left.size())) {
			points.add(left.get(i));
		}
		points.add(left.get(upperBoundary.indexLeft));

		return points;
	}

	protected Boundary getUpperBoundary(List<Point> leftSide,
			List<Point> rightSide) {
		Geometry geometry = new Geometry();
		int pointLeft = geometry.getRightMostPoint(leftSide);
		int pointRight = geometry.getLeftMostPoint(rightSide);

		int nextPointLeft = getNextIndexCounterClockwise(pointLeft,
				leftSide.size());
		int nextPointRight = getNextIndexClockwise(pointRight, rightSide.size());

		int oldPointLeft = 0;
		int oldPointRight = 0;

		do {
			oldPointLeft = pointLeft;
			oldPointRight = pointRight;

			while (geometry.isRight(leftSide, rightSide, pointLeft, pointRight,
					nextPointLeft)) {
				pointLeft = nextPointLeft;
				nextPointLeft = getNextIndexCounterClockwise(pointLeft,
						leftSide.size());
			}

			while (geometry.isLeft(leftSide, rightSide, pointLeft, pointRight,
					nextPointRight)) {

				pointRight = nextPointRight;
				nextPointRight = getNextIndexClockwise(pointRight,
						rightSide.size());
			}

		} while (oldPointLeft != pointLeft || oldPointRight != pointRight);

		return new Boundary(pointLeft, pointRight);
	}

	protected Boundary getLowerBoundary(List<Point> leftSide,
			List<Point> rightSide) {

		Geometry geometry = new Geometry();
		int pointLeft = geometry.getRightMostPoint(leftSide);
		int pointRight = geometry.getLeftMostPoint(rightSide);

		int nextPointLeft = getNextIndexClockwise(pointLeft, leftSide.size());
		int nextPointRight = getNextIndexCounterClockwise(pointRight,
				rightSide.size());

		int oldPointLeft = 0;
		int oldPointRight = 0;

		do {
			oldPointLeft = pointLeft;
			oldPointRight = pointRight;

			while (geometry.isLeft(rightSide, leftSide, pointRight, pointLeft,
					nextPointLeft)) {
				pointLeft = nextPointLeft;
				nextPointLeft = getNextIndexClockwise(pointLeft,
						leftSide.size());
			}

			while (geometry.isRight(rightSide, leftSide, pointRight, pointLeft,
					nextPointRight)) {
				pointRight = nextPointRight;
				nextPointRight = getNextIndexCounterClockwise(pointRight,
						rightSide.size());
			}

		} while (oldPointLeft != pointLeft || oldPointRight != pointRight);

		return new Boundary(pointLeft, pointRight);
	}

	protected int getNextIndexClockwise(int index, int length) {
		int newIndex = index + 1;
		if (newIndex == length) {
			newIndex = newIndex - length;
		}
		if (index == newIndex)
			return -1;
		return newIndex;
	}

	protected int getNextIndexCounterClockwise(int index, int length) {
		int newIndex = index - 1;
		if (newIndex < 0) {
			newIndex = newIndex + length;
		}
		if (index == newIndex)
			return -1;
		return newIndex;
	}

	protected DividedPoints dividePoints(List<Point> points) {
		int grenze = points.size() / 2;
		List<Point> left = points.subList(0, grenze);
		List<Point> right = points.subList(grenze, points.size());
		return new DividedPoints(left, right);
	}

	protected class Boundary {
		public int indexLeft;
		public int indexRight;

		public Boundary(int indexLeft, int indexRight) {
			super();
			this.indexLeft = indexLeft;
			this.indexRight = indexRight;
		}

	}

	/**
	 * A customized comperator, to sort the points for the merge hull algorithm.
	 * 
	 * @author julia
	 * 
	 */
	protected class ComparableMergeHull implements Comparator<Point> {
		@Override
		public int compare(Point o1, Point o2) {
			if (o1.getX() > o2.getX())
				return 1;
			if (o1.getX() < o2.getX())
				return -1;
			return 0;
		}
	}

	protected class DividedPoints {
		List<Point> leftPoints;
		List<Point> rightPoints;

		public DividedPoints(List<Point> leftPoints, List<Point> rightPoints) {
			super();
			this.leftPoints = leftPoints;
			this.rightPoints = rightPoints;
		}

	}
}
